package com.hot100;


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class Solution148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode A = sortList(head);
        ListNode B = sortList(tmp);
        return merge(A,B);
    }

    public ListNode merge(ListNode A, ListNode B) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (A!=null&&B!=null) {
            if (A.val > B.val) {
                cur.next = B;
                B= B.next;
            } else {
                cur.next = A;
                A = A.next;
            }
            cur = cur.next;
        }
        cur.next = A==null?B:A;
        return head.next;
    }
}
